/*
 * =====================================================================================
 *       Filename:  dict.c
 *         Author:  MIEN
 *    Description:  哈希表实现的字典
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dict.h"

static int _dictNextPower(int size)
{
    int n = DICT_DEFAULT_SIZE;
    while (n < size) {
        n *= 2;
    }
    if (n > DICT_MAXIMUM_SIZE)
        n = DICT_MAXIMUM_SIZE;
    return n;
}

dictTable *dictCreateWithSize(dictType *type, int size)
{
    size = _dictNextPower(size);
    dictTable *dt = (dictTable *) malloc(sizeof(dictTable));
    dt->type = type;
    dt->ht = calloc(size, sizeof(dictNode*));
    dt->size = size;
    dt->sizemask = dt->size - 1;
    dt->used = 0;
    return dt;
}

dictTable *dictCreate(dictType *type)
{
    return dictCreateWithSize(type, DICT_DEFAULT_SIZE);
}

void dictFree(dictTable *dt)
{
    int i = 0;
    dictNode *t, *node = NULL;
    for (i = 0; i < dt->size; i++) {
        node = dt->ht[i];
        while (node != NULL) {
            t = node;
            node = node->next;
            if (dt->type->keyDel) dt->type->keyDel(t->key);
            if (dt->type->valDel) dt->type->valDel(t->val);
            free(t);
        }
    }
    free(dt->ht);
    free(dt);
}

void *dictGet(dictTable *dt, void *key)
{
    unsigned int hashcode = dt->type->keyHash(key);
    int idx = hashcode & dt->sizemask;
    dictNode *node = dt->ht[idx];
    while (node != NULL) {
        if (!dt->type->keyCompare(key, node->key))
            return node->val;
        node = node->next;
    }
    return NULL;
}

static void _dictResize(dictTable *dt)
{
    int size0 = dt->size;
    dictNode **ht0 = dt->ht;

    dt->size = _dictNextPower(dt->used);
    dt->sizemask = dt->size - 1;
    dt->ht = calloc(dt->size,  sizeof(dictNode*));
    
    int i;
    for (i = 0; i < size0; i++) {
        dictNode *node0 = ht0[i], *t;
        while (node0 != NULL) {
            unsigned int hashcode = dt->type->keyHash(node0->key);
            int idx = hashcode & dt->sizemask;
            t = node0;
            node0 = node0->next;
            t->next = dt->ht[idx];
            dt->ht[idx] = t;
        }
    }
    free(ht0);
}

void dictSet(dictTable *dt, void *key, void *val)
{
    if (dt->used > dt->size && dt->size < DICT_MAXIMUM_SIZE) {
        _dictResize(dt);
    }

    unsigned int hashcode = dt->type->keyHash(key);
    int idx = hashcode & dt->sizemask;
    dictNode *node = dt->ht[idx];
    while (node != NULL) {
        if (!dt->type->keyCompare(key, node->key)) {
            void *t = node->val;
            node->val = dt->type->valDup ? dt->type->valDup(val) : val;
            if (dt->type->valDel)
                dt->type->valDel(t);
            return;
        }
        node = node->next;
    }
    node = malloc(sizeof(dictNode));
    node->key = dt->type->keyDup ? dt->type->keyDup(key) : key;
    node->val = dt->type->valDup ? dt->type->valDup(val) : val;
    node->next = dt->ht[idx];
    dt->used++;
    dt->ht[idx] = node;
}

void dictDel(dictTable *dt, void *key)
{
    unsigned int hashcode = dt->type->keyHash(key);
    int idx = hashcode & dt->sizemask;
    dictNode *prev = NULL;
    dictNode *node = dt->ht[idx];
    while (node != NULL) {
        if (!dt->type->keyCompare(key, node->key)) {
            if (prev == NULL) {
                dt->ht[idx] = node->next;
            }
            else {
                prev->next = node->next;
            }
            if (dt->type->keyDel) dt->type->keyDel(node->key);
            if (dt->type->valDel) dt->type->valDel(node->val);
            free(node);
            dt->used--;
            return;
        }
        prev = node;
        node = node->next;
    }
}

static unsigned int _dictStringHash(void *key)
{
    unsigned int seed = 1313;
    unsigned int hash = 0;
    char *str = (char *) key;

    while (*str) {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

static int _dictStringCompare(void *key1, void *key2)
{
    return strcmp((char*) key1, (char*) key2);
}

static void *_dictStringCopy(void *str)
{
    int len = strlen(str);
    char *copy = malloc(len + 1);
    memcpy(copy, str, len);
    copy[len] = '\0';
    return copy;
}

static void _dictObjectDel(void *str)
{
    free(str);
}

/* 字符串为键的字典 */
dictType dictTypeStringKey = {
    _dictStringHash,
    _dictStringCompare,
    _dictStringCopy,
    _dictObjectDel,
    NULL,
    NULL,
};

/* 字符串为键和值的字典 */
dictType dictTypeStringKeyVal = {
    _dictStringHash,
    _dictStringCompare,
    _dictStringCopy,
    _dictObjectDel,
    _dictStringCopy,
    _dictObjectDel,
};

/* 字符串为键,并且要释放值的字典 */
dictType dictTypeStringKeyFreeVal = {
    _dictStringHash,
    _dictStringCompare,
    _dictStringCopy,
    _dictObjectDel,
    NULL,
    _dictObjectDel,
};

